// 链表
// function LinkedNode(item) {
//     this.data = item
//     this.next = null
// }

class LinkedNode {
    constructor(data) {
        this.data = data;  // 节点的数据域
        this.prev = null;  // 节点的指针域
        this.next = null;  // 节点的指针域
    }
}

export class LinkedList {
    constructor(arr) {
        this.size = 0;  // 单链表的长度
        this.head = new LinkedNode('head');  // 表头节点
        this.currNode = '';  // 当前节点的指向
        if (Array.isArray(arr)) {
            this.copyFrom(arr)
        }
    }

    // 获取链表的长度
    getLength() {
        return this.size
    }

    // 判断链表是否为空
    isEmpty() {
        return this.size === 0
    }

    find(item) {
        let currNode = this.head;
        while (currNode && (currNode.data !== item)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    last() {
        let currNode = this.head;
        while (currNode.next) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // 从当前位置向前移动 n 个节点。
    advance(n, currNode = this.head) {
        this.currNode = currNode;

        while ((n--) && this.currNode.next) {
            this.currNode = this.currNode.next;
        }

        return this.currNode;
    }
    // 向单链表中插入元素
    insert(item, element) {
        let itemNode = this.find(item);

        if (!itemNode) {  // 如果item元素不存在
            return;
        }

        let newNode = new LinkedNode(element);

        newNode.next = itemNode.next; // 若currNode为最后一个节点，则currNode.next为空
        itemNode.next = newNode;

        this.size++;
    }
    append(element) {
        var item = new LinkedNode(element)  //创建一个新节点
        // 把新的节点放在链表里面去（放在最后一个的后面）
        var currNode = this.last()  //找到链表的最后一个节点
        currNode.next = item

        this.size++  //因为新插入了一个链表，让链表的长度+1


    }
    // 在单链表中删除一个节点
    remove(item) {
        if (!this.find(item)) {  // item元素在单链表中不存在时
            return;
        }

        // 企图删除头结点
        if (item === 'head') {
            if (!(this.isEmpty())) {
                return;
            } else {
                this.head.next = null;
                return;
            }
        }

        let currNode = this.head;

        while (currNode.next.data !== item) {
            // 企图删除不存在的节点
            if (!currNode.next) {
                return;
            }
            currNode = currNode.next;
        }


        currNode.next = currNode.next.next;
        this.size--;
    }
    delete(element) {
        // 先遍历，找到需要删除节点的位置

        // 找到该节点的上一个指针，找到后将该节点的上一个指针next改成指向下一个节点
        // 长度-1
        // 方法1：
        /*var leftNode = null
        var currNode = this.head

        while (currNode.data != element) {  //不是所要寻找的元素就让它继续走
            leftNode = currNode
            currNode = currNode.next
        }
        leftNode.next = currNode.next
        this.size -- */
        // 方法2：
        var currNode = this.head
        while (currNode.next.data != element) {  //currNode永远比while循环快一步
            currNode = currNode.next  //currNode是一个指针，在此处后移
        }
        currNode.next = currNode.next.next
        this.size--

    }
    copyFrom(arr) {
        arr.forEach(t => this.append(t))

    }
    // 单链表的遍历显示
    display() {
        let result = '';
        let currNode = this.head;

        while (currNode) {
            result += currNode.data;
            currNode = currNode.next;
            if (currNode) {
                result += '->';
            }
        }
        console.log(result);
    }

    // 判断链表是否有环，使用了快慢指针，
    // 如果快指针走到最后为null，说明链表没有环，如果两个指针在某个时刻相等了，则说明链表有环。
    isLoop() {
        // 使用快慢指针
        var p = this.head
        var q = this.head

        while (q) {
            p = p.next
            if (p.next) {
                q = q.next.next
            }
            if (p === q) {
                console.log('this list has rings')
                return true
            }
        }

        console.log('this list has no rings')
        return flase
    }

    reverse() {
        var currNode = this.head  //指向链表的头指针
        while (currNode) {
            currNode = currNode.next
        }

    }

}

let ll = new LinkedList([1, 2, 3, 4]) //[1, 2, 3, 4]
// ll.from('')
ll.delete(3)
// ll.advance(1)
ll.insert(2, 5)
ll.display()
// console.log()
var myList = new LinkedList(['A', 'B', 'C', 'D', 'E', 'F', 'G'])


var C = myList.find('C')
var G = myList.last()
G.next = C
let f = myList.isLoop()
console.log(f)


// 现在链表有环

// 上述链表代码的测试
// 最好使用循环，往里面加数据
// var slist = new singleLinked()

// var arr = [1001, 1234, 1006, 7788, 5512, 6129]
// for (var i = 0; i < arr.length; i++) {
//     slist.append(arr[i])
// }
// slist.display()
// slist.delate(1001)
// slist.display()
